#include "util.h"
#include <algorithm>

namespace sylar {
namespace ds {

static const uint32_t s_prime_size = 1250;
static const uint32_t s_prime_list[] = {
	103, 211, 313, 419, 521, 631, 733, 839, 941, 1049, 1151, 1259, 1361, 1471, 1579, 1693, 
	1801, 1907, 2011, 2113, 2221, 2333, 2437, 2539, 2647, 2749, 2851, 2953, 3061, 3163, 3271, 3373, 
	3491, 3593, 3697, 3803, 3907, 4013, 4127, 4229, 4337, 4441, 4547, 4649, 4751, 4861, 4967, 5077, 
	5179, 5281, 5387, 5501, 5623, 5737, 5839, 5953, 6067, 6173, 6277, 6379, 6481, 6599, 6701, 6803, 
	6907, 7013, 7121, 7229, 7331, 7433, 7537, 7639, 7741, 7853, 7963, 8069, 8171, 8273, 8377, 8501, 
	8609, 8713, 8819, 8923, 9029, 9133, 9239, 9341, 9461, 9587, 9689, 9791, 9901, 10007, 10111, 10223, 
	10331, 10453, 10559, 10667, 10781, 10889, 11003, 11117, 11239, 11353, 11467, 11587, 11717, 11839, 11959, 12097, 
	12227, 12373, 12497, 12637, 12781, 12911, 13043, 13177, 13309, 13451, 13591, 13729, 13873, 14029, 14173, 14321, 
	14479, 14627, 14779, 14929, 15083, 15241, 15401, 15559, 15727, 15887, 16057, 16223, 16411, 16603, 16787, 16963, 
	17137, 17317, 17491, 17669, 17851, 18041, 18223, 18413, 18617, 18839, 19031, 19231, 19427, 19661, 19861, 20063, 
	20269, 20477, 20693, 20903, 21121, 21341, 21557, 21773, 21991, 22229, 22453, 22679, 22907, 23143, 23399, 23633, 
	23873, 24113, 24359, 24611, 24859, 25111, 25367, 25621, 25889, 26153, 26417, 26683, 26951, 27239, 27527, 27803, 
	28087, 28387, 28687, 28979, 29269, 29567, 29863, 30169, 30491, 30803, 31121, 31469, 31793, 32117, 32441, 32771, 
	33107, 33457, 33797, 34141, 34483, 34841, 35201, 35569, 35933, 36293, 36671, 37039, 37423, 37799, 38177, 38561, 
	38953, 39343, 39749, 40151, 40559, 40973, 41387, 41801, 42221, 42649, 43093, 43541, 43987, 44449, 44909, 45361, 
	45817, 46279, 46747, 47221, 47699, 48179, 48661, 49157, 49663, 50177, 50683, 51193, 51713, 52237, 52769, 53299, 
	53849, 54401, 54949, 55501, 56081, 56659, 57241, 57829, 58411, 58997, 59611, 60209, 60821, 61441, 62057, 62683, 
	63311, 63949, 64591, 65239, 65899, 66569, 67247, 67927, 68611, 69313, 70009, 70717, 71429, 72161, 72883, 73613, 
	74353, 75109, 75869, 76631, 77417, 78193, 78977, 79769, 80567, 81373, 82189, 83023, 83857, 84697, 85549, 86413, 
	87281, 88169, 89051, 89959, 90863, 91781, 92699, 93629, 94573, 95527, 96487, 97453, 98429, 99431, 100447, 101467, 
	102497, 103529, 104579, 105649, 106721, 107791, 108869, 109961, 111091, 112207, 113341, 114479, 115631, 116789, 117959, 119159, 
	120371, 121577, 122819, 124067, 125311, 126583, 127849, 129169, 130469, 131777, 133097, 134437, 135787, 137147, 138547, 139939, 
	141353, 142771, 144203, 145661, 147137, 148609, 150097, 151603, 153133, 154667, 156217, 157793, 159389, 160997, 162611, 164239, 
	165883, 167543, 169219, 170921, 172633, 174367, 176123, 177887, 179671, 181499, 183317, 185153, 187009, 188891, 190783, 192697, 
	194647, 196597, 198571, 200569, 202577, 204613, 206699, 208787, 210901, 213019, 215153, 217307, 219491, 221707, 223939, 226183, 
	228451, 230743, 233069, 235439, 237821, 240203, 242617, 245071, 247529, 250007, 252509, 255043, 257611, 260189, 262807, 265451, 
	268123, 270821, 273551, 276293, 279073, 281867, 284689, 287537, 290419, 293329, 296269, 299239, 302261, 305297, 308359, 311447, 
	314569, 317717, 320899, 324113, 327401, 330679, 333989, 337339, 340723, 344153, 347609, 351097, 354619, 358181, 361763, 365411, 
	369067, 372763, 376501, 380267, 384079, 387953, 391847, 395767, 399727, 403729, 407783, 411883, 416011, 420191, 424397, 428657, 
	432959, 437293, 441667, 446087, 450557, 455093, 459647, 464251, 468899, 473597, 478339, 483127, 487973, 492853, 497801, 502781, 
	507809, 512891, 518047, 523261, 528509, 533801, 539141, 544543, 550007, 555521, 561079, 566693, 572387, 578117, 583903, 589751, 
	595687, 601651, 607669, 613747, 619897, 626113, 632381, 638717, 645131, 651587, 658111, 664693, 671353, 678077, 684869, 691721, 
	698641, 705631, 712693, 719821, 727021, 734303, 741661, 749081, 756593, 764171, 771853, 779573, 787427, 795307, 803269, 811337, 
	819457, 827677, 835957, 844321, 852769, 861299, 869927, 878629, 887423, 896299, 905269, 914327, 923471, 932749, 942079, 951553, 
	961069, 970687, 980401, 990211, 1000117, 1010129, 1020233, 1030439, 1040747, 1051157, 1061677, 1072301, 1083031, 1093871, 1104811, 1115879, 
	1127039, 1138363, 1149749, 1161263, 1172893, 1184653, 1196501, 1208507, 1220599, 1232809, 1245149, 1257611, 1270193, 1282903, 1295737, 1308707, 
	1321813, 1335043, 1348409, 1361903, 1375531, 1389301, 1403239, 1417279, 1431461, 1445797, 1460267, 1474873, 1489627, 1504537, 1519591, 1534787, 
	1550141, 1565651, 1581311, 1597129, 1613123, 1629259, 1645559, 1662029, 1678657, 1695457, 1712437, 1729591, 1746893, 1764377, 1782043, 1799867, 
	1817873, 1836053, 1854439, 1873013, 1891753, 1910677, 1929793, 1949111, 1968611, 1988299, 2008189, 2028277, 2048569, 2069069, 2089781, 2110679, 
	2131793, 2153111, 2174647, 2196401, 2218367, 2240551, 2262959, 2285597, 2308463, 2331557, 2354873, 2378423, 2402209, 2426233, 2450531, 2475061, 
	2499821, 2524859, 2550133, 2575663, 2601437, 2627473, 2653753, 2680297, 2707109, 2734181, 2761529, 2789161, 2817077, 2845279, 2873743, 2902483, 
	2931527, 2960861, 2990497, 3020431, 3050681, 3081203, 3112069, 3143197, 3174641, 3206393, 3238463, 3270863, 3303607, 3336649, 3370043, 3403783, 
	3437827, 3472211, 3506939, 3542009, 3577459, 3613237, 3649397, 3685949, 3722809, 3760039, 3797641, 3835621, 3873983, 3912749, 3951881, 3991441, 
	4031369, 4071701, 4112431, 4153561, 4195117, 4237069, 4279453, 4322287, 4365511, 4409183, 4453291, 4497839, 4542829, 4588271, 4634173, 4680527, 
	4727339, 4774613, 4822361, 4870589, 4919323, 4968517, 5018203, 5068411, 5119097, 5170289, 5222011, 5274257, 5327017, 5380303, 5434109, 5488459, 
	5543387, 5598823, 5654813, 5711399, 5768513, 5826251, 5884523, 5943373, 6002849, 6062891, 6123563, 6184799, 6246671, 6309143, 6372253, 6435983, 
	6500369, 6565379, 6631033, 6697357, 6764333, 6831991, 6900337, 6969343, 7039093, 7109497, 7180597, 7252409, 7324939, 7398191, 7472177, 7546901, 
	7622371, 7698619, 7775623, 7853383, 7931921, 8011247, 8091361, 8172293, 8254019, 8336569, 8419967, 8504183, 8589241, 8675137, 8761889, 8849521, 
	8938019, 9027407, 9117697, 9208879, 9300983, 9394001, 9487949, 9582829, 9678667, 9775457, 9873223, 9971957, 10071679, 10172399, 10274129, 10376881, 
	10480661, 10585483, 10691353, 10798267, 10906253, 11015339, 11125547, 11236831, 11349203, 11462699, 11577329, 11693111, 11810059, 11928173, 12047473, 12167951, 
	12289631, 12412541, 12536669, 12662047, 12788669, 12916559, 13045729, 13176187, 13307951, 13441031, 13575449, 13711249, 13848379, 13986887, 14126767, 14268043, 
	14410729, 14554847, 14700401, 14847433, 14995913, 15145909, 15297371, 15450353, 15604867, 15760931, 15918541, 16077727, 16238507, 16400927, 16564963, 16730617, 
	16897963, 17066981, 17237651, 17410039, 17584141, 17759983, 17937583, 18116963, 18298139, 18481157, 18665981, 18852641, 19041203, 19231627, 19423951, 19618199, 
	19814381, 20012543, 20212691, 20414819, 20618981, 20825177, 21033433, 21243769, 21456221, 21670787, 21887507, 22106387, 22327463, 22550743, 22776251, 23004017, 
	23234077, 23466419, 23701103, 23938133, 24177523, 24419341, 24663557, 24910211, 25159333, 25410943, 25665071, 25921723, 26180953, 26442817, 26707249, 26974397, 
	27244141, 27516607, 27791833, 28069757, 28350521, 28634027, 28920371, 29209601, 29501723, 29796743, 30094717, 30395669, 30699629, 31006627, 31316699, 31629883, 
	31946209, 32265683, 32588351, 32914237, 33243383, 33575827, 33911587, 34250717, 34593227, 34939169, 35288569, 35641477, 35997893, 36357877, 36721483, 37088729, 
	37459649, 37834253, 38212607, 38594741, 38980691, 39370501, 39764237, 40161881, 40563517, 40969171, 41378873, 41792669, 42210601, 42632729, 43059067, 43489679, 
	43924579, 44363861, 44807507, 45255593, 45708149, 46165241, 46626917, 47093219, 47564177, 48039839, 48520247, 49005457, 49495553, 49990511, 50490449, 50995363, 
	51505319, 52020377, 52540589, 53066011, 53596703, 54132703, 54674041, 55220791, 55773017, 56330767, 56894077, 57463031, 58037669, 58618067, 59204269, 59796353, 
	60394333, 60998293, 61608299, 62224391, 62846669, 63475177, 64109939, 64751041, 65398577, 66052577, 66713107, 67380259, 68054087, 68734667, 69422069, 70116301, 
	70817477, 71525677, 72240947, 72963377, 73693019, 74429951, 75174257, 75926027, 76685321, 77452181, 78226711, 79008983, 79799081, 80597087, 81403061, 82217143, 
	83039323, 83869733, 84708431, 85555523, 86411093, 87275207, 88147967, 89029471, 89919769, 90818983, 91727173, 92644457, 93570943, 94506653, 95451721, 96406253, 
	97370327, 98344033, 99327479, 100320793, 101324009, 102337289, 103360679, 104394289, 105438247, 106492667, 107557601, 108633193, 109719529, 110816731, 111924899, 113044157, 
	114174611, 115316359, 116469527, 117634241, 118810597, 119998717, 121198709, 122410697, 123634813, 124871167, 126119897, 127381123, 128654983, 129941543, 131240983, 132553397, 
	133878937, 135217727, 136569913, 137935613, 139314977, 140708131, 142115249, 143536409, 144971789, 146421521, 147885739, 149364623, 150858283, 152366933, 153890609, 155429537, 
	156983839, 158553779, 160139327, 161740721, 163358141, 164991767, 166641703, 168308123, 169991219, 171691139, 173408083, 175142173, 176893597, 178662541, 180449167, 182253689, 
	184076227, 185917003, 187776179, 189653983, 191550563, 193466089, 195400763, 197354791, 199328341, 201321689, 203334907, 205368257, 207421957, 209496179, 211591141, 213707057, 
	215844149, 218002619, 220182731, 222384563, 224608427, 226854557, 229123117, 231414371, 233728543, 236065831, 238426501, 240810767, 243218891, 245651101, 248107619, 250588697, 
	253094593, 255625543, 258181811, 260763631, 263371271, 266004989, 268665041, 271351699, 274065221, 276805901, 279573971, 282369719, 285193427, 288045389, 290925863, 293835131, 
	296773507, 299741243, 302738659, 305766079, 308823743, 311912059, 315031181, 318181511, 321363331, 324576991, 327822763, 331100999, 334412011, 337756163, 341133761, 344545121, 
	347990579, 351470489, 354985217, 358535081, 362120471, 365741683, 369399101, 373093093, 376824043, 380592307, 384398239, 388242223, 392124701, 396045961, 400006421, 404006503, 
	408046571, 412127047, 416248369, 420410917, 424615027, 428861183, 433149809, 437481337, 441856157, 446274721, 450737471, 455244899, 459797357, 464395333, 469039297, 473729699, 
	478467019, 483251693, 488084221, 492965087, 497894741, 502873729, 507902513, 512981549, 518111381, 523292519, 528525457, 533810723, 539148859, 544540357, 549985763, 555485629, 
	561040489, 566650897, 572317423, 578040611, 583821061, 589659283, 595555879, 601511447, 607526593, 613601887, 619737931, 625935311, 632194711, 638516677, 644901871, 651350897, 
	657864407, 664443061, 671087519, 677798413, 684576463, 691422229, 698336461, 705319859, 712373119, 719496851, 726691897, 733958831, 741298423, 748711423, 756198571, 763760593, 
	771398213, 779112197, 786903353, 794772437, 802720187, 810747389, 818854867, 827043433, 835313873, 843667021, 852103741, 860624797, 869231081, 877923421, 886702679, 895569739, 
	904525441, 913570717, 922706429, 931933511, 941252849, 950665379, 960172033, 969773767, 979471513, 989266231, 999158921, 1009150517, 1019242027, 1029434479, 1039728829, 1050126127, 
	1060627423, 1071233701
};

static const uint32_t* s_prime_end = s_prime_list + s_prime_size;

PrimeGenerator::PrimeGenerator()
    :m_cur(s_prime_list) {
}

uint32_t PrimeGenerator::getIndex() const {
    return m_cur - s_prime_list;
    //uint32_t rt = ((uint64_t)m_cur - (uint64_t)s_prime_list) / 4;
    //std::cout << "index=" << rt << " this=" << this << std::endl;
    //return rt;
}
void PrimeGenerator::setIndex(uint32_t idx) {
    m_cur = s_prime_list + idx;
    //uint32_t rt = ((uint64_t)m_cur - (uint64_t)s_prime_list) / 4;
    //std::cout << "index2=" << idx << " " << rt << " this=" << this << std::endl;
}

uint32_t PrimeGenerator::upperValue(uint32_t v, uint32_t skip) {
    m_cur = std::upper_bound(s_prime_list, s_prime_end, v);
    if(m_cur != s_prime_end) {
        if(m_cur + skip >= s_prime_end) {
            m_cur = s_prime_end - 1;
        } else {
            m_cur = m_cur + skip;
        }
        return *m_cur;
    } else {
        m_cur = s_prime_end - 1;
        return *m_cur;
    }
}

uint32_t PrimeGenerator::getValue() {
    if(m_cur != s_prime_end) {
        return *m_cur;
    }
    return 0;
}

uint32_t PrimeGenerator::nextValue() {
    if(m_cur != s_prime_end) {
        ++m_cur;
        if(m_cur != s_prime_end) {
            return *m_cur;
        }
    }
    return 0;
}

uint32_t PrimeGenerator::prevValue() {
    if(m_cur != s_prime_list) {
        --m_cur;
        return *m_cur;
    }
    return 0;
}

bool PrimeGenerator::hasNext() {
    return m_cur != s_prime_end;
}

bool PrimeGenerator::hasNext(uint32_t dist) {
    return m_cur + dist < s_prime_end;
}

bool PrimeGenerator::hasPrev() {
    return m_cur != s_prime_list;
}

std::string RandomStringGenerator::Gen(uint32_t size) {
    static std::string TEXT ="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    static uint32_t SIZE = TEXT.size();

    std::string rt;
    for(uint32_t i = 0; i < size; ++i) {
        rt.append(1, TEXT[rand() % SIZE]);
    }
    return rt;
}

}
}
